package LeetCode.exercise;

import java.util.LinkedList;
import java.util.Queue;

public class LC733 {
    public static void main(String[] args) {

    }
    int[] dx = new int[]{0, 0, 1, -1};
    int[] dy = new int[]{1, -1, 0, 0};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int target = image[sr][sc];
        if(target == color){
            return image;
        }
        int m = image.length, n = image[0].length;
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{sr, sc});
        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int x = tmp[0], y = tmp[1];
            image[x][y] = color;
            for(int i = 0; i < 4; i++){
                if(x + dx[i] < m && y + dy[i] < n && target == image[x + dx[i]][y + dy[i]]){
                    q.offer(new int[]{x + dx[i], y + dy[i]});
                }
            }
        }
        return image;
    }
}
